class Solution {
public:
    /**
     * min edit cost
     * @param str1 string字符串 the string
     * @param str2 string字符串 the string
     * @param ic int整型 insert cost
     * @param dc int整型 delete cost
     * @param rc int整型 replace cost
     * @return int整型
     dp[i][j] 代表 word1 中前 i 个字符，变换到 word2 中前 j 个字符，最短需要操作的次数
     
     
     1.动态规划：dp[i][j]表示word1的前i个字符编辑成word2的前j个字符需要的最小操作数
2.初始状态：dp[i][0] = i，i次删除；dp[0][i] = i，i次插入
3.过渡公式：
当i字符等于j字符时：dp[i][j] = dp[i-1][j-1]，不需要额外操作
当i字符不等于j字符时：dp[i][j] = Math.min(insert, delete, replace)
int insert = dp[i][j-1] + 1; i个编辑成j-1个字符，再插入一个j
int delete = dp[i-1][j] + 1; i-1个编辑成j个字母，再删除一个i
int replace = dp[i-1][j-1] + 1; i-1个编辑成j-1个字母，再将i替换成
     */
    int minEditCost(string str1, string str2, int ic, int dc, int rc) {
        // write code here
        int len1=str1.size()+1;
        int len2=str2.size()+1;
        vector<vector<int>> dp(len1,vector<int>(len2,0));
        for(int i=0;i<len1;i++)
        {
            dp[i][0]=i*dc;
        }
        for(int j=0;j<len2;j++)
        {
            dp[0][j]=j*ic;
        }
        for(int i=1;i<len1;i++)  //
        
        {
            for(int j=1;j<len2;j++)
            {
          // dp[i][j]=min(dp[i-1][j]+dc,dp[i][j-1]+ic);
          //  dp[i][j]=min(dp[i][j],dp[i-1][j-1]+rc);
                if(str1[i-1]==str2[j-1])  ///注意这里是 i-1==j-1
                {
                    dp[i][j]=dp[i-1][j-1];
                }
                else
                {
     
                    dp[i][j]=min(dp[i-1][j]+dc,dp[i][j-1]+ic);
                    dp[i][j]=min(dp[i][j],dp[i-1][j-1]+rc);
                    
       
                    
                }
             }
        }
        return dp.back().back();
    }
};